class SudokuSolver:
    def __init__(self, grid):
        self.grid = grid  # 保存数独的二维数组
        # 初始化行、列、宫格的数字集合
        self.rows = [set() for _ in range(9)]
        self.cols = [set() for _ in range(9)]
        self.boxes = [set() for _ in range(9)]
        # 填充初始数字
        for row in range(9):
            for col in range(9):
                num = self.grid[row][col]
                if num != 0:
                    self.rows[row].add(num)
                    self.cols[col].add(num)
                    self.boxes[(row // 3) * 3 + (col // 3)].add(num)

    def is_valid(self, row, col, num):
        """检查在 (row, col) 填入 num 是否合法"""
        box_index = (row // 3) * 3 + (col // 3)
        return (
            num not in self.rows[row] and
            num not in self.cols[col] and
            num not in self.boxes[box_index]
        )

    def find_empty(self):
        """找到下一个空白格子（值为 0 的位置），优先选择候选数字最少的格子"""
        min_candidates = 10  # 候选数字的最小数量（初始值为大于 9 的数）
        target_row, target_col = -1, -1

        for row in range(9):
            for col in range(9):
                if self.grid[row][col] == 0:
                    # 计算当前格子的候选数字数量
                    candidates = 0
                    for num in range(1, 10):
                        if self.is_valid(row, col, num):
                            candidates += 1
                    # 如果候选数字更少，则更新目标格子
                    if candidates < min_candidates:
                        min_candidates = candidates
                        target_row, target_col = row, col
                    # 如果候选数字为 0，说明当前格子无解，直接返回
                    if candidates == 0:
                        return (row, col)
        return (target_row, target_col) if min_candidates < 10 else None

    def backtrack(self):
        """回溯算法核心"""
        empty = self.find_empty()  # 找到空白格子
        if not empty:
            return True  # 所有格子已填满，数独已解

        row, col = empty
        for num in range(1, 10):  # 尝试填入 1-9
            if self.is_valid(row, col, num):
                # 填入数字并更新集合
                self.grid[row][col] = num
                self.rows[row].add(num)
                self.cols[col].add(num)
                self.boxes[(row // 3) * 3 + (col // 3)].add(num)

                if self.backtrack():  # 递归尝试下一步
                    return True

                # 回溯，撤销当前填入
                self.grid[row][col] = 0
                self.rows[row].remove(num)
                self.cols[col].remove(num)
                self.boxes[(row // 3) * 3 + (col // 3)].remove(num)

        return False  # 无解时触发回溯

    def solve(self):
        """启动回溯算法并返回解决后的数独"""
        if self.backtrack():  # 如果成功解决
            return self.grid  # 返回解决后的数独
        else:
            return None  # 若无解，返回 None

    def print_grid(self):
        """打印数独，按照 3x3 宫格格式"""
        for i in range(9):
            if i % 3 == 0 and i != 0:  # 每 3 行打印分隔线
                print("-" * 21)
            for j in range(9):
                if j % 3 == 0 and j != 0:  # 每 3 列打印分隔线
                    print("|", end=" ")
                print(str(self.grid[i][j]) if self.grid[i][j] != 0 else ".", end=" ")
            print()  # 换行


if __name__ == '__main__':
    """
    数独解题
    """
    sudoku_grid = [
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 1, 0, 0, 2],
        [0, 0, 3, 0, 4, 0, 5, 6, 0],
        [0, 0, 0, 0, 3, 0, 0, 0, 0],
        [0, 0, 0, 5, 0, 0, 0, 0, 0],
        [0, 7, 0, 0, 0, 0, 0, 0, 8],
        [0, 0, 0, 7, 0, 0, 0, 0, 1],
        [0, 0, 5, 0, 0, 8, 0, 0, 0],
        [6, 0, 4, 0, 0, 0, 0, 3, 0]
    ]

    solver = SudokuSolver(sudoku_grid)
    print("初始数独：")
    solver.print_grid()

    solved_grid = solver.solve()  # 获取解决后的数独
    if solved_grid:
        print("\n解决后的数独：")
        solver.print_grid()
    else:
        print("\n无解")